function KMeans () {

    /**
     * Function to calculate cluster members' mean value, must be overrided before `cluster` function call. 
     *
     * @param {*} members
     */
    this.meanCalcFunc = function ( members ) {
        throw new Error( "This function must be overrided before Cluster runs. " );
    }


    /**
     * Function to calculate two members' difference value, must be overrided before `cluster` function call. 
     *
     * @param {*} a
     * @param {*} b
     */
    this.diffCalcFunc = function ( a, b ) {
        throw new Error( "This function must be overrided before Cluster runs. " );
    }


    /**
     * Cluster the inputs using k-means algorithm, wrt maxDiffThreshold. 
     *
     * @param {*} inputs
     * @param {*} maxDiffThreshold
     * @returns
     */
    this.clusterize = function ( inputs, maxDiffThreshold ) {

        if ( inputs.length < 2 ) {
            throw new Error( "Vertex Normal Clustering only works for normals length more than 2. " )
        }

        // face normals clustering using k-means, k = 1 ~ n
        let k = 1;
        let targetReached = false;
        let lastClusters = [];
        let currClusters = [];
        let centers = [];

        // k-means implementation
        while ( k < inputs.length ) {

            let convergent = false;

            while ( !convergent ) {

                // generate centers, if no centers exist, use the first k normals as center
                centers = [];
                if ( lastClusters.length === 0 ) {
                    for ( let i = 0; i < k; i++ ) {
                        centers.push( inputs[ i ] ); // need copy
                    }
                } else {
                    for ( let i = 0; i < lastClusters.length; i++ ) {
                        centers.push( this.meanCalcFunc( Array.from( lastClusters[ i ].members.values() ) ) );
                    }
                }

                // initialize clusters with centers
                currClusters = [];
                for ( let i = 0; i < k; i++ ) {
                    currClusters.push( new Cluster( centers[ i ] ) );
                }

                // cluster face normals
                for ( let i = 0; i < inputs.length; i++ ) {
                    clusterObject( inputs[ i ], currClusters );
                }

                // if lengths are not equal, it is the first time of clustering, need to do second iteration
                if ( currClusters.length !== lastClusters.length ) {

                    convergent = false;
                    lastClusters = Array.from( currClusters ); // copy, not just assign
                    continue;

                }

                // when the clustering result is the same as last iteration, this clustering process has reached convergence
                convergent = true;
                for ( let i = 0; i < currClusters.length; i++ ) {
                    const currCluster = currClusters[ i ];
                    const lastCluster = lastClusters[ i ];
                    // if the currClusters is the same as lastCluster, it is convergent
                    // otherwise it is not convergent yet
                    if ( !currCluster.compareWith( lastCluster ) ) {
                        convergent = false;
                    }
                }

                lastClusters = Array.from( currClusters );
            }

            // when the clusters are convergent (stable), calc max angle of each cluster and judge for threshold
            targetReached = true;
            for ( let i = 0; i < currClusters.length; i++ ) {
                const cluster = currClusters[ i ];
                if ( getMaxDiff( Array.from( cluster.members ) ) > maxDiffThreshold ) {
                    targetReached = false;
                }
            }

            // if each cluster reaches normalAngleThreshold, return
            if ( targetReached ) {
                return currClusters;
            }

            // otherwise clustering again using k+1
            k++;
            lastClusters = [];
            currClusters = [];

            // if there is no answer when iteration ends, possibly because the input has only two normals and they are very different
            if ( k === inputs.length ) {
                for ( const input of inputs ) {
                    let cluster = new Cluster( input );
                    cluster.members.push( input );
                    currClusters.push( cluster );
                }
                return currClusters;
            }
        }

    }


    var getMaxDiff = ( members ) => {
        let max = 0;
        let m = 0;
        let n = m + 1;
        while ( m < members.length - 1 ) {
            n = m + 1;
            while ( n < members.length ) {
                let val = this.diffCalcFunc( members[ m ], members[ n ] );
                max = Math.max( val, max );
                n++;
            }
            m++;
        }
        return max;
    }


    var clusterObject = ( obj, clusters ) => {
        let minVal = Infinity;
        let targetCluster;
        for ( let i = 0; i < clusters.length; i++ ) {
            const cluster = clusters[ i ];
            let val = this.diffCalcFunc( obj, cluster.center );
            if ( val < minVal ) {
                minVal = val;
                targetCluster = cluster;
            }
        }
        targetCluster.members.push( obj );
    }


    /**
     * class Cluster
     *
     * @author Yuan Yao
     * @date 2020-04-09
     * @param {*} center
     */
    function Cluster ( center ) {
        this.center = center;
        this.members = [];
        return this;
    }

    Cluster.prototype = Object.create( {

        constructor: Cluster,

        compareWith: function ( cluster ) {
            for ( const member of this.members ) {
                if ( cluster.members.indexOf( member ) < -1 ) return false;
            }
            for ( const member of cluster.members ) {
                if ( this.members.indexOf( member ) < -1 ) return false;
            }
            return true;
        }

    } );

}